package com.yan_jiu_sheng.LeetCodeHot100.AC;


/**
 * https://leetcode.cn/problems/minimum-window-substring/?envType=study-plan-v2&envId=top-100-liked
 * 通过
 * 动态滑动窗口
 *
 * @author yulongTian
 * @create 2024-05-27 11:25
 */
public class Test12 {
    public static void main(String[] args) {
        System.out.println(minWindow("ab", "A"));
    }

    public static String minWindow(String s, String t) {
        if (s.length() < t.length()) {
            return "";
        }
        int[] tCount = new int[52];
        int[] sCount = new int[52];
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            char k = s.charAt(i);
            if (c >= 'A' && c <= 'Z') {
                tCount[c - 'A' + 26]++;
            } else {
                tCount[c - 'a']++;
            }

            if (k >= 'A' && k <= 'Z') {
                sCount[k - 'A' + 26]++;
            } else {
                sCount[k - 'a']++;
            }
        }
        if (s.length() == t.length()) {
            if (check(tCount, sCount)) {
                return s;
            } else {
                return "";
            }
        }
        int leftPoint = 0;
        int rightPoint = leftPoint + t.length() - 1;
        int len = s.length();
        String res = s;
        while (rightPoint < len) {
            while (!check(sCount, tCount)) {
                rightPoint++;
                if (rightPoint >= len) {
                    break;
                }
                char c = s.charAt(rightPoint);
                if (c >= 'A' && c <= 'Z') {
                    sCount[c - 'A' + 26]++;
                } else {
                    sCount[c - 'a']++;
                }
            }
            if (rightPoint >= len) {
                break;
            }
            if (rightPoint - leftPoint + 1 < res.length()) {
                res = s.substring(leftPoint, rightPoint + 1);
            }
            while (check(sCount, tCount)) {
                char k = s.charAt(leftPoint);
                if (k >= 'A' && k <= 'Z') {
                    sCount[k - 'A' + 26]--;
                } else {
                    sCount[k - 'a']--;
                }
                leftPoint++;
                if (leftPoint >= rightPoint) {
                    break;
                }
            }
            if (rightPoint - leftPoint + 2 < res.length()) {
                res = s.substring(leftPoint - 1, rightPoint + 1);
            }
        }
        if (s.equals(res)) {
            int[] ssCount = new int[52];
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (c >= 'A' && c <= 'Z') {
                    ssCount[c - 'A' + 26]++;
                } else {
                    ssCount[c - 'a']++;
                }
            }
            return check(ssCount, tCount) ? s : "";
        }

        return res;
    }

    public static boolean check(int[] a, int[] b) {
        for (int i = 0; i < b.length; i++) {
            if (b[i] != 0 && a[i] < b[i]) {
                return false;
            }
        }
        return true;
    }

}
